package edu.leti.example;

public class Heap {

	private MyNode[] heapArray;

	private int maxSize;

	private int currentSize; // number of items in array

	public int getCurrentSize(){
		return currentSize;
	}

	/**
	 * Конструктор массива пирамиды с фиксированным размером
	 * @param mx размер массива пирамиды
	 */
	public Heap(int mx) {
		maxSize = mx;
		currentSize = 0;
		heapArray = new MyNode[maxSize];
	}

	/**
	 * Удалить корневой узел из кучи и обновить порядок остальных узлов в массиве пирамиды
	 * @return бывший корневой узел из кучи
	 */
	public MyNode remove() 
	{ 
		MyNode root = heapArray[0];
		heapArray[0] = heapArray[--currentSize];
		trickleDown(0);
		return root;
	}

	/**
	 * Просеивание вниз некоторого узла в пирамиду
	 * @param index индекс просеиваемого узла
	 */
	public void trickleDown(int index) {
		int largerChild;
		MyNode top = heapArray[index]; 
		while (index < currentSize / 2)
		{
			int leftChild = 2 * index + 1;
			int rightChild = leftChild + 1;
			// find larger child
			if (rightChild < currentSize
					&& 
					heapArray[leftChild].getKey() < heapArray[rightChild]
					                                          .getKey())
				largerChild = rightChild;
			else
				largerChild = leftChild;

			if (top.getKey() >= heapArray[largerChild].getKey())
				break;

			heapArray[index] = heapArray[largerChild];
			index = largerChild; 
		}
		heapArray[index] = top;
	}

	/**
	 * Отобразить пирамиду на экране
	 */
	public void displayHeap() {
		int nBlanks = 32;
		int itemsPerRow = 1;
		int column = 0;
		int currentIndex = 0; 
		while (currentSize > 0)
		{
			if (column == 0) 
				for (int k = 0; k < nBlanks; k++)
					System.out.print(' ');
			System.out.print(heapArray[currentIndex].getKey());

			if (++currentIndex == currentSize) // done?
				break;

			if (++column == itemsPerRow) // end of row?
			{
				nBlanks /= 2; 
				itemsPerRow *= 2; 
				column = 0; 
				System.out.println(); 
			} else
				for (int k = 0; k < nBlanks * 2 - 2; k++)
					System.out.print(' '); // interim blanks
		} 
	}

	/**
	 * Отобразить массив пирамиды на экране
	 */
	public void displayArray() {
		for (int j = 0; j < maxSize; j++)
			System.out.print(heapArray[j].getKey() + " ");
		System.out.println("");
	}

	/**
	 * Получить массив пирамиды
	 * @return массив содержащий пирамиду
	 */
	public int[] getArray() {
		int[] result = new int[heapArray.length];

		for (int j = 0; j < maxSize; j++)
			result[j] = heapArray[j].getKey();

		return result;
	}

	/**
	 * Вставить новый узел в кучу
	 * @param index индекс для вставки
	 * @param newNode добавляемый узел
	 */
	public void insertAt(int index, MyNode newNode) {
		heapArray[index] = newNode;
	}
	
	/**
	 * Получить заданный узел
	 * @param index индекс элемента
	 * @return currentNode возвращаемый узел
	 */
	public MyNode getCurrentNode(int index) {
		return (MyNode)heapArray[index];
	}

	/**
	 * Увеличить текущий размер массива пирамиды
	 */
	public void incrementSize() {
		currentSize++;
	}

}



